// PrintBoundaryNodes.cpp : Defines the entry point for the console application.

#include "stdafx.h"
#include <iostream>
#include <stack>
#include <queue>
#include <deque>
using namespace std;

#define null 0
struct TreeNode
{
    int value;
    TreeNode *left, *right;

    TreeNode() { };

    TreeNode(int v)
    {
        value=v;
        left=right=null;
    };
};

// Given a binary tree, print all edge nodes (boundary nodes) counter-clockwise.
//
// Algorithm: Pre-order traverse the tree:
//  1. Before visit the first leaf, output every visiting node (left-most edge nodes)
//  2. Output all leaf nodes (buttom edge nodes)
//  3. After visit the last leaf, output the stack content (right-most edge nodes)
//
// Assumption: The root must be either null or have 2 child.
//
// Iteration

// Count leaf nodes
// Recursion
int CountLeaf(TreeNode *root)
{
    if(!root) return 0;
    if(!root->left&&!root->right) return 1;

    return CountLeaf(root->left)+CountLeaf(root->right);
}

// Iteration: Pre-order traversal
int CountLeaf_Iterative(TreeNode *root)
{
    if(!root) return 0;
    stack<TreeNode *> s;
    s.push(root);
    int count=0;
    while(!s.empty())
    {
        TreeNode *p=s.top();
        s.pop();
        if(!p->left&&!p->right) ++count;
        if(p->right) s.push(p->right);
        if(p->left) s.push(p->left);
    }

    return count;
}

void BTBoundary_CounterClockwise_Iterative(TreeNode *root)
{
    if(!root) return;
    stack<TreeNode *> s;
    s.push(root);
    int leafCount=CountLeaf(root), last=0; // 0:from up, 1:from left, 2:from right
    bool foundFirstLeaf=false;
    while(!s.empty())
    {
        TreeNode *p=s.top();
        if(last==0)
        {
            // Left-most edge nodes
            if(!foundFirstLeaf&&(p->left||p->right)) cout<<p->value<<" ";

            // Buttom edge nodes
            if(!p->left&&!p->right)
            {
                cout<<p->value<<" ";
                foundFirstLeaf=true;
                --leafCount;
            }

            if(p->left)
            {
                last=0;
                s.push(p->left);
            }
            else last=1;
        }
        else if(last==1)
        {
            if(p->right)
            {
                last=0;
                s.push(p->right);
            }
            else last=2;
        }
        else if(last==2)
        {
            // Right-most edge nodes
            if(!leafCount && (p->left||p->right) && p!=root) cout<<p->value<<" ";

            s.pop();
            if(!s.empty() && s.top()->left==p) last=1;
            else last=2;
        }
    }  
}


// Recursion: Pre-order traversal
void BTBoundary_CounterClockwise_Recursive(TreeNode *root, TreeNode *node, bool &foundFirstLeaf, int &leafCount)
{
    if(!node) return;

    if(!foundFirstLeaf && (node->left||node->right)) cout<<node->value<<" ";

    if(!node->left&&!node->right)
    {
        cout<<node->value<<" ";
        foundFirstLeaf=true;
        --leafCount;
    }

    BTBoundary_CounterClockwise_Recursive(root,node->left,foundFirstLeaf,leafCount);
    BTBoundary_CounterClockwise_Recursive(root,node->right,foundFirstLeaf,leafCount);

    if(!leafCount && (node->left||node->right) && node!=root)
    {
        cout<<node->value<<" "; // prevent the root from being output twice
    }
}

void BTBoundary_CounterClockwise_Recursive(TreeNode *root)
{
    if(!root) return;

    bool foundFirstLeaf=false;
    int leafCount=CountLeaf(root);
    BTBoundary_CounterClockwise_Recursive(root,root,foundFirstLeaf,leafCount);
}

//Test Case:
//    ______________28_______________
//   /                               \
//  4____                        ____69
//       \                      /
//      __8__                __56__
//     /     \              /      \
//   _7      12__         _34     _27__
//  /            \       /       /     \
// 5__          _13    _2      _3      39
//    \        /      /       /
//     6      11     10       9
//
//Output: 28, 4, 8, 7, 5, 6, 11, 10, 9, 39, 27, 56, 69

int _tmain(int argc, _TCHAR* argv[])
{
    return getchar();
}